/*
 *https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/
 *2477. 到达首都的最少油耗
 *medium 吴朝泽 2024.11.13
 *DFS深度优先搜索
*/

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        // 构建邻接表表示树
        int n = roads.size() + 1;  // 节点数
        vector<vector<int>> adj(n);
        
        // 构建图
        for (auto& road : roads) {
            adj[road[0]].push_back(road[1]);
            adj[road[1]].push_back(road[0]);
        }

        // 记录总油耗
        long long totalFuel = 0;
        
        // dfs函数返回当前子树的代表数
        function<int(int, int)> dfs = [&](int node, int parent) -> int {
            int representatives = 1;  // 当前节点的代表自己算一个
            // 遍历所有子节点
            for (int neighbor : adj[node]) {
                if (neighbor == parent) continue;
                
                int subRepresentatives = dfs(neighbor, node);  // 子树的代表数
                representatives += subRepresentatives;  // 累加代表数

                // 计算油耗，每个子树的代表需要的车数
                totalFuel += (long long)ceil((double)subRepresentatives / seats);
            }
            return representatives;
        };

        // 从首都（节点0）开始dfs
        dfs(0, -1);
        
        return totalFuel;
    }
};